package j2024.j202407;

import java.util.*;

public class j0722 {
    Map<Character, Set<Character>> edges = new HashMap<>();
    HashMap<Character,Integer> in = new HashMap<>();
    boolean check;
    public String alienOrder(String[] words) {
        //初始化
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                char ch = words[i].charAt(j);
                in.put(ch,0);
            }
        }
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                add(words[i],words[j]);
                if(check == true){
                    return "";
                }
            }
        }
        //拓补排序
        Queue<Character> q = new LinkedList<>();
        for(char a:in.keySet()){
            if(in.get(a)==0){
                q.add(a);
            }
        }
        StringBuilder ret = new StringBuilder();
        while (!q.isEmpty()){
            char t = q.poll();
            ret.append(t);
            if(!edges.containsKey(t)){
                continue;
            }
            for(char ch:edges.get(t)){
                in.put(ch,in.get(ch)-1);
                if(in.put(ch,in.get(ch))==0){
                    q.add(ch);
                }
            }
        }
        for(char ch:in.keySet()){
            if(in.get(ch)!=0){
                return "";
            }
        }
        return ret.toString();
    }
    public void add(String s1,String s2){
        int n = Math.min(s1.length(),s2.length());
        int i = 0;
        for (; i < n; i++) {
            char c1 = s1.charAt(i),c2 = s2.charAt(i);
            if(s1.charAt(i)!=s2.charAt(i)){
                //c1->c2
                if(!edges.containsKey(c1)){
                    edges.put(c1,new HashSet<>());
                }
                if(!edges.get(c1).contains(c2)){
                    edges.get(c1).add(c2);
                    in.put(c2,in.get(c2)+1);
                }
                break;
            }
        }
        if(i==s2.length() && i<s1.length()){
            check =true;
        }
    }

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        List<StringBuilder> ret = new ArrayList<>();
        int max = -1;
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i)<'0' || str.charAt(i)>'9'){
                continue;
            }else if(str.charAt(i)>='0' && str.charAt(i)<='9'){
                StringBuilder tmp = new StringBuilder();
                while(i<str.length()&& str.charAt(i)>='0' && str.charAt(i)<='9' ){
                    tmp.append(str.charAt(i));
                    i++;
                }
                ret.add(tmp);
                max = Math.max(tmp.length(),max);
            }
        }
        for (int i = 0; i < ret.size(); i++) {
            if(ret.get(i).length()==max){
                System.out.println(ret.get(i).toString());
            }
        }
    }



    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    Queue<int[]> q = new LinkedList<>();
    boolean[][] vis;
    int m,n;
    public int solve (char[][] grid) {
        // write code here
        int count = 0;
        m = grid.length;
        n = grid[0].length;
         vis= new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]=='1' && !vis[i][j]){
                    count++;
                    bfs(grid,i,j);
                }
            }
        }
        return count;
    }
    public void bfs(char[][] grid,int i,int j){
        q.add(new int[]{i,j});
        vis[i][j] = true;
        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0],b = t[1];
            for (int k = 0; k < 4; k++) {
                int x = a+dx[k],y = b+dy[k];
                if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y]=='1'){
                    q.add(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }
    }


    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n][6];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 6; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            Arrays.sort(arr[i]);
            if(arr[i][0]+arr[i][1]>arr[i][2] && arr[i][3]+arr[i][4]>arr[i][5]
            || arr[i][0]+arr[i][2]>arr[i][3] && arr[i][1]+arr[i][4]>arr[i][5]
            || arr[i][0]+arr[i][3]>arr[i][4] && arr[i][1]+arr[i][2]>arr[i][5]
            || arr[i][0]+arr[i][4]>arr[i][5] && arr[i][1]+arr[i][2]>arr[i][3]
            ){
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }
    //611
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int left = 0,right = 0;
        int count = 0;
        for (int i = nums.length-1; i >=2 ; i--) {
            right = i-1;
            left = 0;
            while(left<right){
                if(nums[left]+nums[right] > nums[i]){
                    count+=right-left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return count;
    }
    //LCR 179
    public int[] twoSum(int[] price, int target) {
        int left = 0,right = price.length-1;
        int[] ret = new int[2];
        while(left<right){
            if(price[left]+price[right] == target){
                ret[0] = price[left];
                ret[1] = price[right];
                break;
            }else if (price[left]+price[right] > target){
                right--;
            }else {
                left++;
            }
        }
        return ret;
    }
    //15
    public List<List<Integer>> threeSum(int[] nums) {
        /**
         * 先排序
         * 固定一个数
         * 剩下的数中找两个=-a
         */
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < nums.length; ) {
            if(nums[i]>0){
                break;
            }
            int left = i+1,right = nums.length-1,target = -nums[i];
            while(left<right){
                if(nums[left]+nums[right]>target){
                    right--;
                } else if (nums[left]+nums[right]<target) {
                    left++;
                }else {
                    ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;
                    right--;
                    while(left<right && nums[left]==nums[left-1]){
                        left++;
                    }
                    while(left<right && nums[right]==nums[right+1]){
                        right--;
                    }
                }
            }
            i++;
            while(i<nums.length && nums[i]==nums[i-1]){
                i++;
            }
        }
        return ret;
    }
}
